Multi-protocol Label Switching (MPLS) has emerged as a key technology for service providers. One of the primary applications for MPLS is traffic engineering (TE) (see, Awduche, et al., “Requirements for traffic engineering over MPLS,” IETF RFC 2702, 1997, incorporated herein by reference). MPLS TE capabilities are attractive because they provide the flexibility to control the routing via Label Switched Paths (LSPs).
Traditionally, TE has focused on efficient routing of individual LSPs. However, as network traffic migrates from voice to data (adding to network “churn”), maintaining or improving network efficiency levels is becoming evermore difficult. This is further exacerbated by the fact that data lacks the hierarchical growth structure of voice traffic. Thus, service providers are seeking tools for network-wide engineering and management of their MPLS networks.
In conjunction with standardized signaling protocols such as RSVP (see, Awduche, et al., “Extension to RSVP for LSP tunnels,” IETF draft, 1998, incorporated herein by reference), MPLS provides infrastructure for disruption-free reconfiguration with constructs such as make-before-break. Make-before-break does not guarantee hitless packet delivery by itself. However, when coupled with the resiliency of the client services such as TCP based applications, make-before-break ensures disruption-free reconfiguration in most operational scenarios.
Unfortunately, no network management system exists that employs this reconfigurability infrastructure to improve end-to-end efficiency. Furthermore, no such system exists that operates online and without any service interruption. The process of hitless, network-wide engineering may be referred to as “network tuning.” Note that network tuning can either be proactive to prevent future inefficiencies or reactive in response to specific network events such as failures. Unlike TE, tuning is not a per-LSP parameter—(e.g., bandwidth or, route) tweaking operation but encompasses the end-to-end network operation. The example below illustrates the concept.
Referring initially to FIG. 1, illustrated is an exemplary network of six IP routers, seven links of capacity B and three LSPs L1-L3 of capacity B/2. Let there be a new LSP request between A and C for bandwidth B. In a regular MPLS network, A would reject this request because of insufficient bandwidth to C. However, sufficient capacity does exist in the network, but it is fragmented. A network management system with tuning intelligence could proactively re-engineer the traffic to ensure that the demand is satisfied.
For example, rerouting L2 via A-E-F and L3 via A-B-D would allow the new LSP request to be provisioned along A-C. Thus, by such online tuning, requests that would otherwise have been denied can be satisfied and in the long run, help improve network utilization and lower the capital expenditure.
However, scaling tuning to networks with hundreds of nodes and LSPs presents a serious computational challenge. Furthermore, while MPLS provides the necessary mechanisms to minimize disruption during traffic reconfiguration, it does not provide any intelligence on how one might exploit it. Note that network tuning involves not only determining the routes for the various LSPs (the flow design problem) but more critically, deriving the sequence of LSP rerouting steps that prevents any service disruption (the path migration problem).
Prior work on the flow design problem has focused on the optimal flow assignment without any consideration for path migration. One such example is given in Elwalid, et al., “Online traffic engineering with design-based routing,” in Proceedings of ITC Specialist Workshop, Wurzburg, July 2002 (incorporated herein by reference) and the other references cited therein. The problem of path migration has been studied in the context of optical WDM networks. In Ramamurthy, et al., “Virtual Topology Reconfiguration of Wavelength-routed Optical WDM Networks,” IEEE GLOBECOM Proceedings, 2000 (incorporated herein by reference), a reconfiguration constraint is added to the LP formulation for the flow design problem and Sridharan, et al., “Operating Mesh-Survivable WDM Transport Networks,” SPI Int. Symp. Terabit Optical Networking, November 2000 (incorporated herein by reference) adds a reconfiguration cost to the ILP formulation for network optimization. However, the goal in both is to minimize reconfiguration, and any reconfiguration is still service-disruptive. Bala, et al., “Towards Hitless Reconfiguration in WDM Optical Networks for ATM Transport,” IEEE GLOBECOM Proceedings, 1996 (incorporated herein by reference) proposed a way to achieve hitless reconfiguration assuming sufficient resources to support the union of the original and optimized configuration, an assumption unlikely to hold in practice.
Accordingly, what is needed in the art is a system and method for achieving effective disruption-free network tuning in an MPLS network.